home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 16148 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: news.mel.aone.net.au!Rabbit
  2. From: biggles@c031.aone.net.au (Biggles Cheung)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Bucket sort?!?
  5. Date: Tue, 09 Apr 96 14:14:58 GMT
  6. Message-ID: <4ke0o6$rqo@news.mel.aone.net.au>
  7. References: <Pine.SOL.3.91.960407192931.10206A-100000@jove.acs.unt.edu>
  8. NNTP-Posting-Host: d86-1.cpe.melbourne.aone.net.au
  9. X-Newsreader: News Xpress 2.0 Beta #0
  10.  
  11. In article <Pine.SOL.3.91.960407192931.10206A-100000@jove.acs.unt.edu>, Daniel Lee Mccormick <dlm0001@jove.acs.unt.edu> wrote:
  12. >Hello,
  13. >I'm new to c++ coding and am having a prob. Could someone please post an 
  14. >example of bucket sorting. I'm reading in from a data file into an array, 
  15. >but I'm stumped on the actual sorting part. Any help would be appreciated.
  16. >
  17. >-Daniel
  18.  
  19. Bucket Sort is the same as _Distribution Sort_, so try looking for 
  20. distribution sort in any reference book.
  21.  
  22. I just copy the following example from my lecture note, & hope this helps 
  23. (hope this works :-o )...
  24.  
  25.  
  26. * Sort N records in array a[] whose keys are intergers between 0 and M-1
  27.  
  28.  
  29. distribution(int a[], int N) {
  30.  
  31.   int i, j, count[M], b[N+1];   /* count[] & b[] are temporary arrays 
  32.   
  33.   for (j=0; j<M; j++)
  34.     count[j]= 0;                /* init counts
  35.   for (i=1; i<=N; i++)
  36.     count[a[i]]++;              /* count no. of each key
  37.   for (j=1; j<M; j++)
  38.     count[j] += count[j-1];     /* compute offsets
  39.   for (i=N; i>=1; i--)
  40.     b[count[a[i]]--] = a[i];    /* sort into b backwardly to ensure stability
  41.   for (i=1; i<=N; i++)
  42.     a[i] = b[i];                /* copy back into original array, i.e. a[]
  43. }
  44.  
  45.  
  46. You may find more about Bucket Sort (distribution sort) from ...
  47.  
  48.         Algorithm in C, Robert Sedgewick, Addison Wesley
  49.  
  50.  
  51. _/\/\/\/\/\___/\/\_________________________/\/\_________________________
  52. _/\/\____/\/\__________/\/\/\/\___/\/\/\/\_/\/\_____/\/\/\_____/\/\/\/\_
  53. _/\/\/\/\/\___/\/\___/\/\__/\/\_/\/\__/\/\_/\/\___/\/\/\/\/\_/\/\/\/\___
  54. _/\/\____/\/\_/\/\_____/\/\/\/\___/\/\/\/\_/\/\___/\/\_____________/\/\_
  55. _/\/\/\/\/\___/\/\/\_______/\/\_______/\/\_/\/\/\___/\/\/\/\_/\/\/\/\___
  56. ____________________/\/\/\/\___/\/\/\/\_________________________________
  57.